package com.gxc.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 单词接龙
 * 字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
 *
 * 每一对相邻的单词只差一个字母。
 *  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
 * sk == endWord
 * 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0
 */
public class LadderLength {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        List<Integer>[] graphic = new List[wordList.size()];
        for (int i = 0; i < wordList.size(); i++) {
            graphic[i] = new ArrayList<>();
        }
        int endIndex = -1;
        for (int i = 0; i < wordList.size(); i++) {
            if (wordList.get(i).equals(endWord)) endIndex = i;
            for (int j = i+1; j < wordList.size(); j++) {
                if (judge(wordList.get(i), wordList.get(j))) {
                    graphic[i].add(j);
                    graphic[j].add(i);
                }
            }
        }
        if (endIndex == -1) return 0;

        int step = 1;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visit = new boolean[wordList.size()];
        for (int i = 0; i < wordList.size(); i++) {
            String s = wordList.get(i);
            if (judge(s, beginWord)) {
                queue.add(i);
                visit[i] = true;
            }
        }

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                if (cur == endIndex) return step+1;
                List<Integer> list = graphic[cur];
                for (int j = 0; j < list.size(); j++) {
                    Integer next = list.get(j);
                    if (!visit[next]) {
                        queue.add(next);
                        visit[next] = true;
                    }
                }
            }
            step++;
        }
        return 0;
    }

    private boolean judge(String a, String b) {
        int n = a.length();
        int num = 0 ;
        for (int i = 0; i < n; i++) {
            if (a.charAt(i) != b.charAt(i)) num++;
        }
        return num == 1;
    }

}
